#include<iostream>
#include<vector>

using namespace std;
//Space: O(1)
//Time: O(n^2)
vector<int> bubbleSort(vector<int> array) {
  int end = array.size() - 1;
  bool sorted = false;
  while (!sorted) {
    sorted = true;
    for (int i = 0; i < end; ++i) {
      if (array[i+1] < array[i]) {
        swap(array[i+1], array[i]);
        sorted = false;
      }
    }
    end--;
  }
  return array;
}

int main(int argc, char const *argv[]) {
  vector<int> array = {1, 3, 5, 0, 8, 1, 12, 2, -5};
  for(int i : bubbleSort(array)) {
    cout << i << " ";
  }
  return 0;
}
